# Copyright 2013, Michael H. Goldwasser
#
# Developed for use with the book:
#
#    Data Structures and Algorithms in Python
#    Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
#    John Wiley & Sons, 2013
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.


def find_boyer_moore(T, P):
	"""Return the lowest index of T at which substring P begins (or else -1)."""
	n, m = len(T), len(P)  # introduce convenient notations
	if m == 0: return 0  # trivial search for empty string
	last = {}  # build 'last' dictionary
	for k in range(m):
		last[P[k]] = k  # later occurrence overwrites
	# align end of pattern at index m-1 of text
	i = m - 1  # an index into T
	k = m - 1  # an index into P
	while i < n:
		if T[i] == P[k]:  # a matching character
			if k == 0:
				return i  # pattern begins at index i of text
			else:
				i -= 1  # examine previous character
				k -= 1  # of both T and P
		else:
			j = last.get(T[i], -1)  # last(T[i]) is -1 if not found
			i += m - min(k, j + 1)  # case analysis for jump step
			k = m - 1  # restart at end of pattern
	return -1
